import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Created by forcht on 2018/5/5.
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head==null)return null;
        List<ListNode> list=new ArrayList<>();
        while (head!=null){
            list.add(head);
            head=head.next;
        }
        list.sort(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return Integer.compare(o1.val,o2.val);
            }
        });
        head=list.get(0);
        ListNode node=head;
        for(int i=1;i<list.size();i++){
            node.next=list.get(i);
            node=list.get(i);
        }
        node.next=null;
        return head;
    }
}

  class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
   }
